typedef int ElemSet;
ElemSet **Create2DArray(int row, int col) {
    /* 动态声明row行col列的二维数组 */
    ElemSet *a, **t;
    int i;

    a = (ElemSet *)malloc(sizeof(ElemSet) * row * col);
    t = (ElemSet **)malloc(sizeof(ElemSet *) * row);
    for (i = 0; i < row; i++)
        t[i] = &a[col * i];
    return t;
}

void Free2DArray(ElemSet **t) {
    /* 释放二维数组空间 */
    free(t[0]);
    free(t);
}

int Max(int x, int y) {
    return (x > y) ? x : y;
}

void GetLCS(char x[], int i, char y[], int j, int **l, char *seq, int idx) {
    /* i为x的长度，j为y的长度，l是长度矩阵，当前要处理seq[idx]的值 */
    if (i == 0 || j == 0) {
        return; /* 当前子问题已经没有公共子序列 */
    }
    if (x[i - 1] == y[j - 1]) { /* 当序列长度增加时 */
        seq[idx] = x[i - 1]; /* 收录这个增加的元素 */
        GetLCS(x, i - 1, y, j - 1, l, seq,
               idx - 1); /* 递归解决长度分别减1的子问题 */
    } else if (l[i - 1][j] > l[i][j - 1]) {
        GetLCS(x, i - 1, y, j, l, seq, idx); /* 递归解决x长度减1的子问题 */
    } else {
        GetLCS(x, i, y, j - 1, l, seq, idx); /* 递归解决y长度减1的子问题 */
    }
}

int LCS(char x[], int n, char y[], int m) {
    int **l, maxl, i, j;
    char *seq;

    if (n == 0 || m == 0) {
        return 0; /* 长度为0的序列无子序列 */
    }
    l = Create2DArray(n + 1, m + 1);
    /* 根据递推式计算长度矩阵l[i][j] */
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                l[i][j] = 0;
            } else if (x[i - 1] == y[j - 1]) { /* 注意字符串下标从0开始 */
                l[i][j] = l[i - 1][j - 1] + 1;
            } else {
                l[i][j] = Max(l[i - 1][j], l[i][j - 1]);
            }
        }
    }
    maxl = l[n][m]; /* 最长公共子序列的长度存储在l[n][m]中 */
    seq = (char *)malloc(sizeof(char) * (maxl +
                                         1)); /* 创建存储最长公共子序列的数组 */
    GetLCS(x, n, y, m, l, seq, maxl - 1); /* 获得一个最长公共子序列 */
    seq[maxl] = '\0'; /* 添加字符串结束符 */
    printf("%s\n", seq); /* 打印最长公共子序列 */
    Free2DArray(l);
    free(seq);
    return maxl; /* 返回最长公共子序列的长度 */
}